﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace ChineseRemainderTheorem.Core
{
    public static class ModField
    {
        public static BigInteger ExtendedGreatestCommonDivisor(BigInteger a, BigInteger b, out BigInteger x, out BigInteger y)
        {
            if (a == BigInteger.Zero)
            {
                x = 0;
                y = 1;
                return b;
            }
            else
            {
                BigInteger x1, y1;
                BigInteger d = ExtendedGreatestCommonDivisor(b % a, a, out x1, out y1);
                x = y1 - (b / a) * x1;
                y = x1;
                return d;
            }
        }

        public static void Normalize(ref BigInteger value, BigInteger mod)
        {
            value %= mod;
            if (value < BigInteger.Zero)
            {
                value += mod;
            }
        }

        public static BigInteger ReverseOnField(BigInteger a, BigInteger mod)
        {
            // a*x = 1 (mod m)
            BigInteger x, y;
            BigInteger g = ExtendedGreatestCommonDivisor(a, mod, out x, out y);
            if (g != 1)
            {
                throw new Exception("No reverse");
            }
            else
            {
                return (x % mod + mod) % mod;
            }
        }
    }
}
